/*
 * @Author: zxc
 * @Date: 2020-08-09 18:47:34
 * @LastEditTime: 2020-08-10 20:32:25
 * @LastEditors: zxc
 * @Description: 首先，avl二叉树它可以看作是一个搜索二叉树的子类，
 *                它是一种自平衡树，即它的任意一个节点的左子树和左子树
 *                它们的高度最多相差为1
 *                因为AVL树也是一种BST的原因，所以可以直接扩展BST类
 *
 */
import { Compare, defaultCompare } from "./util";
import { BinarySearchTree } from "./searchtree";
import Nodess from "./nodes";

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};

export class AVLTree extends BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = this.compareFn;
    this.root = null;
  }

  //一个计算节点深度（高度）的方法
  getNodeHeight(node) {
    if (node === null) {
      return -1;
    }
    return (
      Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) +
      1
    );
  }

  /**
   * LL:左子树过高，右旋转
   *
   *       b                           a
   *      / \                         / \
   *     a   e -> rotationLL(b) ->   c   b
   *    / \                             / \
   *   c   d                           d   e
   *
   */
  rotationLL(node) {
    let temp = node.left;
    node.left = temp.right;
    temp.right = node;
    return temp;
  }

  /**
   * RR:右子树过高，左旋转
   *
   *     a                              b
   *    / \                            / \
   *   c   b   -> rotationRR(a) ->    a   e
   *      / \                        / \
   *     d   e                      c   d
   *
   */
  rotationRR(node) {
    let temp = node.right;
    node.right = temp.left;
    temp.left = node;
    return temp;
  }

  /**
   * LR:向右旋转，左子节点深度大于右子节点深度，并且左子节点的右侧过重
   *    处理方法是：先将它变成一个左左的情况，然后再进行一个右旋转
   */
  rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }

  /**
   * RL:向右旋转，右子节点深度大于左子节点深度，并且右子节点的左侧过重
   * 处理方法是：先将它变成一个RR的情况，然后再进行一个LL的右旋转
   */
  rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationRR(node);
  }

  //插入节点
  insert(key) {
    this.root = this.insertNode(this.root, key);
  }
  insertNode(node, key) {
    if (node == null) {
      return new Nodess(key);
    } else if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, key);
    } else {
      return node; //重复键
    }
    // 检查是否否进行树平衡操作
    const balanceFactor = this.getBalanceFactor(node);
    //左子树过高 LR（需要插入子节点大于左侧子节点，即左侧子节点右侧较重，否则即是左左情况）
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
        // Left left case
        node = this.rotationLL(node);
      } else {
        // Left right case
        return this.rotationLR(node);
      }
    }
    // 右子树过高，RL（需要插入子节点大于右侧子节点，即右侧子节点左侧较重，否则即是右右情况）
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
        node = this.rotationRR(node);
      } else {
        return this.rotationRL(node);
      }
    }
    return node;
  }

  getBalanceFactor(node) {
    const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDifference) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
  }

  removeNode(node, key) {
    node = super.removeNode(node, key); // {1}
    if (node == null) {
      return node;
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    //左侧的树过高
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // LL
      if (
        this.getBalanceFactor(node.left) === BalanceFactor.BALANCED ||
        this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
      ) {
        return this.rotationLL(node);
      }
      // LR
      if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationLR(node.left);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // RR
      if (
        this.getBalanceFactor(node.right) === BalanceFactor.BALANCED ||
        this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
      ) {
        return this.rotationRR(node);
      }
      // RL
      if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationRL(node.right);
      }
    }
    return node;
  }
}

// let ks = new AVLTree();
// ks.insert(12);
// ks.insert(2);
// ks.insert(22);
// ks.insert(17);
// ks.insert(18);
// ks.remove(2)
// // ks.insert(24)
// // ks.insert(22)
// // ks.insert(4)
// // ks.insert(5)
// console.log(ks);
